package com.atguigu.KnightTour;

import java.awt.*;
import java.util.ArrayList;

/*
*
* 创建一个棋盘二维数组
* 将当前位置设置为已经访问，根据当前位置，计算马儿还能走哪些位置，宁放入到一个集合种Arraylist，最多八个位置
* 遍历ArrayList所有位置看看哪一个可以走通
* 判断马尔是否完成任务没使用step和应该走的步数进行比较秒如果没有达到，则表示任务没有完成，将整个棋盘置0.
*
*使用贪心算法优化
*
*
* */
public class KnightTourAlgorithm {
    private static int X;//表示列数
    private static int Y;//表示行数
    //创建一个数组，标记棋盘的各个位置是否被访问过
    private static boolean visited[];
    private static  boolean finisnhed;//棋盘的位置都被访问过了
    public static void main(String[] args) {
        X=8;
        Y=8;
        int row=1;
        int column=1;
        int[][] chessboard=new int[X][Y];
        visited=new boolean[X*Y];
        //测试一个花费时间
        long start = System.currentTimeMillis();
        travelsalChessBoard(chessboard,row-1,column-1,1);
        long end = System.currentTimeMillis();
        System.out.println("耗时："+(end-start)/1000+"秒");

        System.out.println("输出棋盘情况");
        for (int[] rows : chessboard) {
            for (int step : rows) {
                System.out.print(step+"\t");
            }
            System.out.println();

        }

    }
    public  static ArrayList<Point> next(Point curPoint){
        //创建一个Arraylist
        ArrayList<Point> ps = new ArrayList<>();
        Point p1 = new Point();
        //5
        if((p1.x=curPoint.x-2)>=0&&(p1.y=curPoint.y-1)>=0){
            ps.add(new Point(p1));
        }
        //6
        if((p1.x=curPoint.x-1)>=0&&(p1.y=curPoint.y-2)>=0){
            ps.add(new Point(p1));
        }//7
        if((p1.x=curPoint.x+1)<X&&(p1.y=curPoint.y-2)>=0){
            ps.add(new Point(p1));
        }
        //0
        if((p1.x=curPoint.x+2)<X&&(p1.y=curPoint.y-1)>=0){
            ps.add(new Point(p1));
        }
        //1
        if((p1.x=curPoint.x+2)<X&&(p1.y=curPoint.y+1)<Y){
            ps.add(new Point(p1));
        }

        //2
        if((p1.x=curPoint.x+1)<X&&(p1.y=curPoint.y+2)<Y){
            ps.add(new Point(p1));
        }
        //3
        if((p1.x=curPoint.x-1)>=0&&(p1.y=curPoint.y+2)<Y){
            ps.add(new Point(p1));
        }
        //4
        if((p1.x=curPoint.x-2)>=0&&(p1.y=curPoint.y+2)<Y){
            ps.add(new Point(p1));
        }
        return ps;
    }
    public static void travelsalChessBoard(int[][] chessboard,int row,int column,int step){
         chessboard[row][column]=step;
         visited[row*X+column]=true;//标记该位置
        //记录还能走的位置
        ArrayList<Point> ps = next(new Point(column, row));
        //遍历ps
        while (!ps.isEmpty()){
            Point p=ps.remove(0);//取出一个可以走的位置
            //判断该点是否访问过
            if(!visited[p.y*X+p.x]){//还没有访问过
                travelsalChessBoard(chessboard,p.y,p.x,step+1);
            }
        }
        //判断是否完成了任务
        if(step<X*Y&&!finisnhed){
            chessboard[row][column]=0;
            visited[row*X+column]=false;
        }else{
            finisnhed=true;
        }
    }
}